#include<iostream>
// #include<unordered_set>
// #include<unordered_map>
#include<vector>
using namespace std;

template<class T>
struct my_hash
{
    size_t operator()(const T& x) const
    {
        return (size_t)x;
    }
};

template<>
struct my_hash<string>
{
    size_t operator()(const string& s) const
    {
        size_t res = 0, p = 1;
        for(auto e : s)
        {
            res += e * p;
            p *= 131;
        }
        return res;
    }
};

template<class T>
struct hash_table_node
{
    T _val;
    hash_table_node* _next;

    hash_table_node(const T& x = T(), hash_table_node* next = nullptr)
        :_val(x)
        ,_next(next)
    {}
};

template<class T, class Hash = my_hash<T>>
class HashTable
{
    typedef hash_table_node<T> node;
    vector<node*> _h;
    int _size = 0;
public:
    HashTable(int n = 10)
        :_h(n)
    {}
    ~HashTable()
    {
        for(int i = 0; i < _h.size(); i++)
            if(_h[i])
            {
                node* j = _h[i];
                while(j)
                {
                    node* next = j->_next;
                    delete j;
                    j = next;
                }
            }
    }
    HashTable(const HashTable& h)
        :_h(h._h.size())
        ,_size(h._size)
    {
        for(int i = 0; i < h._h.size(); i++)
            for(node* j = h._h[i]; j; j = j->_next)
            {
                node* cur = new node(j->_val);
                cur->_next = _h[i];
                _h[i] = cur;
            }
    }
    HashTable& operator= (const HashTable& h)
    {
        if(this != &h)
        {
            HashTable tmp(h);
            swap(tmp);
        }
        return *this;
    }
    pair<int, node*> _find(const T& x)
    {
        Hash get_hash;
        int pos = get_hash(x) % _h.size();
        for(node* i = _h[pos]; i; i = i->_next)
            if(i->_val == x)
                return {pos, i};
        return {pos, nullptr};
    }

    bool find(const T& x)
    {
        if(_find(x).second)   
            return true;
        return false;
    }
    void swap(HashTable& h)
    {
        _h.swap(h._h);
        std::swap(_size, h._size);
    }
    bool insert(const T& x)
    {
        if(_size >= 0.7 * _h.size())
        {
            Hash get_hash;
            vector<node*> new_t(2 * _h.size());
            for(int i = 0; i < _h.size(); i++)
            {
                if(_h[i])
                {
                    node* j = _h[i];
                    while(j)
                    {
                        int pos = get_hash(j->_val) % new_t.size();
                        node* next = j->_next;
                        j->_next = new_t[pos];
                        new_t[pos] = j;
                        j = next;
                    }
                }
            }
            _h.swap(new_t);
        }
        auto p = _find(x);
        if(p.second) return false;
        int pos = p.first;
        node* cur = new node(x, _h[pos]);
        _h[pos] = cur;
        _size++;
        return true;
    }

    bool erase(const T& x)
    {
        auto p = _find(x);
        if(!p.second) return false;
        int pos = p.first;
        node* cur = p.second;
        if(_h[pos] == cur) 
            _h[pos] = _h[pos]->_next;
        else{
            node* j = _h[pos];
            while(j->_next != cur)
                j = j->_next;
            j->_next = j->_next->_next;
        }
        delete cur;
        _size--;
        return true;
    }
};